package chunzhao.guanglianda;

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.PrintWriter;
import java.util.Scanner;

/**
 * @Classname T2021412
 * @Description TODO
 * @Date 2021/4/21 18:33
 * @Created by yin
 */
public class T2021412 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] nums = new int[n];
        int[][] dp = new int[n + 1][k + 1];// dp[i][j] 表示第访问到第i罐的时候，吃了k个时的最大相邻罐头和
        for (int i = 0; i < nums.length; i++) {
            nums[i] = scanner.nextInt();
        }
        for (int i = 0; i <= k; i++) {
            dp[1][k] = Math.max(nums[0] - k, 0);
        }
        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.max(dp[i - 1][0], nums[i - 1] + nums[i - 2]);
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                for (int l = 2; l <= i; l++) {
                    // 如果取了这一个那最大值就是A
                    int choose = Math.max(dp[l - 1][j-1], nums[l - 1] + nums[l - 2] - 1);
                    // 如果没有取这一个
                    int notChoose = Math.max(dp[l - 1][j]-1, nums[l - 1] + nums[l - 2]);
                    dp[l][j] = Math.min(notChoose,choose);
                }
            }
        }
        int ans = Integer.MAX_VALUE;
        for (int i = 1; i <= k; i++) {
            ans = Math.min(dp[n][i], ans);
        }
        System.out.println(ans);
    }

}

